package 力扣.树.层序遍历;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class 二叉树每一层的平均值 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);

        TreeNode root21 = new TreeNode(9);
        TreeNode root22 = new TreeNode(20);

        TreeNode root31 = new TreeNode(15);
        TreeNode root32 = new TreeNode(7);

        root.left = root21;
        root.right = root22;
        root22.left = root31;
        root22.right = root32;
        List<Double> doubles = averageOfLevels(root);
        System.out.println(doubles);
    }

    /**
        队列FIFO ；每一层的平均数
     */
    public static List<Double> averageOfLevels(TreeNode root) {
        List<Double> ans = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        if (root != null){
            deque.offerFirst(root);
        }
        while (deque.size() > 0){
            int size = deque.size();
            int aveOne = 0;
            for (int i = 0; i < size; i++) {
                TreeNode last = deque.pollLast();
                aveOne += last.val;
                if (last.left != null){
                    deque.offerFirst(last.left);
                }
                if (last.right != null){
                    deque.offerFirst(last.right);
                }
            }
            ans.add((double)aveOne/size);
        }
        return ans;
    }
}
